Caching hierarchies are commonly used to accelerate the delivery of content to end users. A caching hierarchy includes different tiers with one or more peers per tier. Each peer represents one or more servers that are deployed to different network locations. In a caching hierarchy, the peers store copies of the same content at each of the different locations in order to serve the content to end users from the location that is most proximate to the end user.
The caching hierarchy tiers allow for a fan-out distribution of the content. Requests for content that is not cached at a first tier funnels through to different tiers until reaching a final tier where only a limited number of peers have access to an origin site where an original copy of the content is stored.
Most content delivery networks (CDNs) operate using some tiered caching hierarchy. A CDN operates multiple points-of-presence (PoPs) with each PoP representing a set of caching servers operating from or serving content to a specific geographic region. The PoPs, and by extension the servers of each PoP, function as peers that can be configured to different hierarchical caching tiers for different customer content. For example, the CDN may have PoPs in Los Angeles, Dallas, New York, and Florida. A first customer origin server may be located somewhere in California. Accordingly, the CDN could designate the Dallas, New York, and Florida PoPs to a first caching tier and the Los Angeles PoP to a second caching tier. When a request for the first customer content is received at a first caching tier PoP and the content is not cached therein, the first caching tier PoP does not access the first customer origin directly to retrieve the content, but rather the Los Angeles PoP as the second caching tier. When the Los Angeles PoP also does not have a cached copy of the first customer content, the Los Angeles PoP retrieves the content from the first customer origin and distributes the content to the first tier PoP for distribution to the requesting end user. If a second customer origin server was located somewhere in Texas, the CDN would designate the Los Angeles, New York, and Florida PoPs as first tier PoPs and the Dallas PoP as the second tier PoP for the second customer content. From these two examples, it should be evident that designation of nodes to tiers can change depending on which customer's content is requested.
Each of the peers can be configured with one or more next-tier lists. The next-tier list identifies the next lower tier within the multi-tier hierarchy that a peer should access in order to retrieve requested content of a particular customer that is not present in cache. Continuing from the example above, the next-tier list for the New York PoP would identify the Los Angeles PoP as the next PoP to access when the first customer content is requested and not present in cache. The next-tier list would change to identify the Dallas PoP as the next PoP to access when the second customer content is requested and not present in cache.
Any tier within a multi-tier hierarchy can have multiple peers. The multiple peers at a given tier can be used to facilitate failover. For instance, a failure may prevent a first peer at a first tier from accessing a configured next-tier peer at a second tier. Failover allows the first peer at the first tier to pass the request to a different second peer at the first tier so that the second peer can attempt to access the next-tier peer at the second tier on behalf of the first peer. The second peer may be located in a different geographic region than the first peer. As a result, the second peer may have different functioning network pathways or better performing network pathways to connect to the peer at the second tier.
To enable such failover, the various peers are configured with a same-tier list in addition to the above mentioned next-tier list. The same-tier list identifies other peers in the same tier to failover to when a particular peer is unable to access a peer at a lower tier identified in its next-tier list.
FIG. 1 illustrates peers at a particular tier performing failover. For simplicity, the next-tier and the same-tier lists are combined into one next-peer list (e.g., reference marker 110). The first peer identified in the combined next-peer list identifies the lower tier peer that is accessed when requested content is not present in local cache of a particular peer. The subsequent peers identified in the next-peer list identify other peers in the same tier as the particular peer that the particular peer fails over to when the particular peer is unable to access the lower tier peer.
As shown in FIG. 1, peer 120 is unable to access the lower level tier 130. According to the next-peer list, the peer 120 fails over to peer 140. Peer 140 is also unable to access the lower level tier 130. Based on the next-peer list configured to peer 140, peer 140 fails over to peer 150 which successfully accesses the lower level tier 130 and retrieves the requested content. The requested content is then passed back through the multi-tier hierarchy for distribution back to the requesting user.
The primary shortcoming to failover based on next-peer lists is the potential for creating an infinite loop when the next-peer lists of different peers point to one another. FIG. 2 conceptually illustrates an infinite loop forming within a particular tier of a caching hierarchy performing failover by way of the configured next-peer lists.
FIG. 2 presents a three-tier caching hierarchy. Three second tier peers are configured with next-peer lists to facilitate failover if needed. A first tier peer receives (at 210) a user request. The first tier peer does not have requested content cached or the content is not cacheable and needs to be retrieved from a next tier. Accordingly, the first tier peer passes (at 220) the request to the first second tier peer. The first second tier peer also does not have the requested content cached. The first second tier peer attempts (at 230) to retrieve the content from the third tier peer, but a failure prevents the first second tier peer from doing so. The first second tier peer then performs failover according to its next-peer list and forwards (at 240) the request to a second peer at the second tier.
The second peer also does not have the content cached. According to its configured next-peer list, the second peer passes the (at 250) the request back to the first peer. The request then continually passes back-and-forth between the first peer and the second peer at the caching hierarchy second tier.
There is therefore a need for loop detection and loop prevention when passing messaging across a hierarchy of different peers organized to different tiers. More specifically, there is a need to implement failover in a manner that does not create loops within a caching hierarchy or other hierarchy comprised of multiple tiers and multiple peers in some of the tiers. To this end, there is a need to elastically find an alternate route to a second tier peer when a first tier peer is unable to access the second tier peer.